#include <iostream>
#include <unordered_map>
#include <list>
using std::cout;
using std::endl;
using std::unordered_map;
using std::list;
class LRUCache{
public:
    LRUCache(int capacity)
    :_capacity(capacity)
    {}

    int get(int key){
        auto it = _cache.find(key);
        if(it != _cache.end()){
            //访问过的置于链表头
            _point.splice(_point.begin(),_point,it->second);
            return key;
        }else{
            return -1;
        }
    }

    void put(int key,int value){
        auto it = _cache.find(key);
        if(it != _cache.end()){
            it->second->_value = value;
            _point.splice(_point.begin(),_point,it->second);
            
        }else{
            if(_point.size() == _capacity){
                auto & del = _point.back();
                _cache.erase(del._key);
                _point.pop_back();
            }

            _point.push_front(Point(key,value));
            _cache.insert(std::make_pair(key,_point.begin()));
        }

    }
private:
    struct Point{
        Point(int x,int y)
        :_key(x)
        ,_value(y)
        {}

        int _key;
        int _value;
    };
    int _capacity;
    list<Point> _point;
    unordered_map<int,list<Point>::iterator> _cache;
};

void test0(){
    LRUCache lru(2);
    lru.put(1,1);
    cout << "get(1) " << lru.get(1) << endl;

    lru.put(2,1);
    cout << "get(2) " << lru.get(2) << endl;
    
    lru.put(1,3);
    cout << "get(1) " << lru.get(1) << endl;

    lru.put(3,3);
    cout << "get(3) " << lru.get(3) << endl;

    cout << "get(2) " << lru.get(2) << endl;

}

int main(int argc, char * argv[])
{
    test0();
    return 0;
}


